package Offer.offer2022;

import domain.TreeNode;

/**
 * 重建二叉树
 */
public class Test06 {

    public static TreeNode rebuildTreeNode(int[] pre, int[] in) {
        if (pre == null || pre.length == 0 ||
                in == null || in.length == 0) {
            throw new RuntimeException("输入不合法");
        }
        return rebuildTreeNode(pre, 0, pre.length - 1, in, 0, in.length - 1);
    }

    public static TreeNode rebuildTreeNode(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
        if (preStart < preEnd || inStart < inEnd) {
            return null;
        }
        int value = pre[preStart];
        TreeNode root = new TreeNode(value);

        int index;
        for (index = inStart; index <= inEnd; index++) {
            if (in[index] == value) {
                break;
            }
        }
        root.left = rebuildTreeNode(pre, preStart + 1, preStart + index - inStart, in, inStart, index - 1);
        root.right = rebuildTreeNode(pre, preStart + index - inStart + 1, preEnd, in, index + 1, inEnd);
        return root;
    }
}
